/*****************************************************************************/
// The realization of Merge sort of asending
// Input an array of numbers.
// Output the asendingly sorted array.
/*****************************************************************************/

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;

void Merge(vector<int> &ivec, int p, int q, int r) {
	int i, j, k;
	int n1 = q-p+1;
	int n2 = r-q;
	vector<int> L,R;
	for ( i = 0; i != n1; ++i )
		L.push_back( ivec[p+i] );
	for ( j = 0; j != n2; ++j )
		R.push_back( ivec[q+j+1] );
	i = 0;
	j = 0;
	for ( k = p; k != r+1; ++k ) {
		if ( i == n1 ) {
			ivec[k] = R[j];
			++j;
		} else if ( j == n2 ) {
			ivec[k] = L[i];
			++i;
		} else if ( L[i] <= R[j] ) {
			ivec[k] = L[i];
			++i;
		} else {
			ivec[k] = R[j];
			++j;
		}
	}
}

void Merge_Sort(vector<int> &ivec, int p, int r) {
	int q;
	if ( p < r ) {
		q = (p + r) / 2;
		Merge_Sort(ivec, p, q);
		Merge_Sort(ivec, q+1, r);
		Merge(ivec, p, q, r);
	} else
		return;
}

int main(){
	int buffer;
	//int counter = 0;
	vector<int> sort;
	cout << "Please input an array of numbers" << endl;
	while ( cin >> buffer ) {
		sort.push_back(buffer);
		//counter++;
	}
	Merge_Sort(sort, 0, sort.size()-1);
	for ( vector<int>::iterator it = sort.begin(); it != sort.end(); ++it)
		cout << *it << "\t";
	cout << endl;
	return 0;
}

